package sort;

public class SmallSum {
    public static void process(int[] arr){
        if (arr==null || arr.length<1){
            return;
        }
        System.out.println(mergeSort(0,arr.length-1,arr));
    }
    public static int mergeSort(int l,int r,int[] arr){
            if (l==r){
                return 0;
            }
            int min = l+((r-l)>>1);


            return mergeSort(min,r,arr)
                    +mergeSort(l,min+1,arr)
                    +merge(l,min,r,arr);
    }
    public static int merge(int l,int min, int r,int[] arr){
        int res = 0;
        int[] help = new int[r-l];
        int p1 = l;
        int p2 = min+1;
        int i =0;
        while (p1<=min && p2<=r){
            res = arr[p1]<arr[p2]?(r-p2+1)*arr[p1]:0;
            help[i++] = arr[p1]<arr[p2]?arr[p1]:arr[p2];
        }
        while (p1<=min){
            help[i++] = arr[p1++];
        }
        while (p2<=r){
            help[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[l+j] = help[j++];
        }
        return res;
    }
}
